P2831 愤怒的小鸟

首先，我们得知道过原点与两点的抛物线解析式：

设该函数解析式为 $y=ax^2+bx+c(a < 0)$且过 $(0,0),(x_1,y_1),(x_2,y_2)$ 三点。

由函数过 $(0,0)$ 得 $c=0$。

函数解析式为 $y=ax^2+bx(a < 0)$

$\begin{cases} {ax_1}^2+bx_1=y_1\\ {ax_2}^2+bx_2=y_2 \end{cases}$

$\begin{cases} a=\frac{y1-bx_1}{{x_1}^2}\\ a=\frac{y2-bx_2}{{x_2}^2} \end{cases}$

$\to \frac{y_1-bx_1}{{x_1}^2}=\frac{y_2-bx_2}{{x_2}^2}$

$\to (y_1-bx_1)* {{x_2}^2}=(y_2-bx_2)*{{x_1}^2}$

$\to y_1*{x_2}^2-bx_1*{x_2}^2=y_2*{x_1}^2-bx_2*{x_1}^2$

$\to bx_2*{x_1}^2-bx_1*{x_2}^2=y_2*{x_1}^2-y_1*{x_2}^2$

$\to bx_1-bx_2=\frac{y_2*{x_1}^2-y_1*{x_2}^2}{x_1x_2}$

$\to b=\frac{y_2*{x_1}^2-y_1*{x_2}^2}{x_1x_2(x_1-x_2)}$

$\to a=\frac{y_1-bx_1}{{x_1}^2}$

$\to a=\frac{x_2*y_1-x_1*y_2}{x_1x_2(x_2-x_1)}$

综上所述，函数解析式为

$y=\frac{x_2*y_1-x_1*y_2}{x_1x_2(x_2-x_1)}x^2+\frac{y_2*{x_1}^2-y_1*{x_2}^2}{x_1x_2(x_1-x_2)}x$

$\text{dfs(x,num,lon)表示处理到第$x$只猪，用了$num$只鸟，剩下$lon$只没有被击中}$

剩下的就容易处理了。

#include <cstdio>
#include <cmath>
#include <iostream>
using namespace std;
#define eps 1e-8
#define Paird pair<double,double>

const int MAXN = 20;
int t , n , m , Ans , s;
struct node{
	double x , y;
}dex[ MAXN + 5 ] , fun[ MAXN + 5 ] , lone[ MAXN + 5 ];
Paird calc( node a , node b ) {
	double A = ( b.x * a.y - a.x * b.y ) / ( a.x * b.x * ( a.x - b.x ) ) , B = ( b.y * a.x * a.x - a.y * b.x * b.x ) / ( a.x * b.x * ( a.x - b.x ) );
	return { A , B };
}

void dfs( int x , int num , int lon ) {
	if( num + lon >= Ans ) return;
	if( x == n + 1 ) {
		Ans = num + lon;	//使用的鸟+剩下的猪各需一只鸟
		return;
	}
	
	for( int i = 1 ; i <= num ; i ++ ) //看这只猪能否被之前的一只鸟击中
		if( fabs( fun[ i ].x * dex[ x ].x * dex[ x ].x + fun[ i ].y * dex[ x ].x - dex[ x ].y ) < eps ) {
			dfs( x + 1 , num , lon );
			return;
		}
	for( int i = 1 ; i <= lon ; i ++ ) {	//与之前剩下的一只猪组成抛物线
		if( fabs( dex[ x ].x - lone[ i ].x ) < eps ) continue; 
		Paird s = calc( dex[ x ] , lone[ i ] );
		if( s.first < 0 ) {
			fun[ num + 1 ] = { s.first , s.second };
			
			node tmp[ MAXN + 5 ];
			for( int k = i ; k <= lon ; k ++ )
				tmp[ k ] = lone[ k ];
			for( int k = i ; k < lon ; k ++ )
				lone[ k ] = lone[ k + 1 ];
			dfs( x + 1 , num + 1 , lon - 1 );
			for( int k = i ; k <= lon ; k ++ )
				lone[ k ] = tmp[ k ];
		}
	}
	lone[ lon + 1 ] = dex[ x ];		//作为剩下的一只猪
	dfs( x + 1 , num , lon + 1 );
}

int main( ) {
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d %d",&n,&m); Ans = n;
		for( int i = 1 ; i <= n ; i ++ )
			scanf("%lf %lf",&dex[ i ].x,&dex[ i ].y);
		dfs( 1 , 0 , 0 );
		printf("%d\n",Ans);
	}
	return 0;
}